package BlackRedTree;

public class Test {
    public static void main(String[] args) {
        int[] arr = {4, 2, 6,1,3,5,15,7,16,14};

        BRTree tree = new BRTree();
        for (int a: arr) {
            tree.insert(a);
        }
        System.out.println(isBlackRed(tree.root));
    }

    //判断是否是红黑树
    public static boolean isBlackRed(BRTree.TreeNode root) {
        if (root == null) {
            return true;
        }
        if (root.color == Color.Red) {
            return false;
        }
        //计算一条路径中黑色节点的数量
        BRTree.TreeNode r = root;
        int num = 0;
        while(r != null) {
            if (r.color == Color.Black) {
                num++;
            }
            r = r.left;
        }
        return isColor(root) && isValue(root) && isNumber(root, num, 0);
    }

    //判断每条路径的黑色节点是否相同
    public static boolean isNumber(BRTree.TreeNode root, int tmp, int cur) {
        if (root == null) {
            return tmp == cur;
        }
        boolean a;
        boolean b;
        if (root.color == Color.Black) {
            cur++;
            a = isNumber(root.left, tmp, cur);
            b = isNumber(root.right, tmp, cur);
            cur--;
        } else {
            a = isNumber(root.left, tmp, cur);
            b = isNumber(root.right, tmp, cur);
        }
        return a && b;
    }

    //判断是否是二叉搜索树
    public static boolean isValue(BRTree.TreeNode root) {
        if (root == null) {
            return true;
        }
        if (root.left != null && root.left.val >= root.val) {
            return false;
        }
        if (root.right != null && root.right.val <= root.val) {
            return false;
        }
        return isValue(root.left) && isValue(root.right);
    }

    //判断是否没有重复的红色节点
    public static boolean isColor(BRTree.TreeNode root) {
        if (root == null) {
            return true;
        }
        if (root.color == Color.Red && root.parent.color == Color.Red) {
            return false;
        }
        return isColor(root.left) && isColor(root.right);
    }
}
